package everydayone.trap;
/**
 * @Date 2020/04/04
 * @author 王光浩
 * @Thinking 使用双指针法。
 */
public class Introduction {
	public int trap(int[] height) {
		if(height.length<3)return 0;
		int front=0;
		int trail;
		int len=height.length;
		int count=0;   //统计能够获取的雨水数
		//找到第一个峰值
		while(front<len-1) {
			if(height[front]>height[++front])break;
		}
		front--;
		if(front==len-1)return 0;
		//统计雨水数
		trail=front+1;
		while(trail<len) {
			//统计深度
			while(trail<len-1)
				if(height[trail]<height[++trail])break; //要么是最大深度右边的第一个要么出界
			//统计高度
			while(trail<len-1)
				if(height[trail]<height[trail+1])trail++;
				else break;
			count+=count(front,trail,height);
			front=trail;
			trail+=1;
		}
		trail--;
		if(trail>front && height[trail]>height[trail-1]) {
			count+=count(front,trail,height);
		}
		return count;
    }
	//统计在first~second之间的雨水数
	private int count(int first,int second,int[] height) {
		if(second>=height.length)return 0;
		int low=Math.min(height[first], height[second]);
		int count=0;
		for(int i=first;i<=second;i++){
			if(height[i]<low)count+=(low-height[i]);
		}
		return count;
	}
}
